1625C - Road Optimization - CodeForces Solution


dp *1700

Please click on ads to support us..

Python Code:

n,l,k=map(int,input().split())
a=list(map(int,input().split()))+[l]
b=list(map(int,input().split()))+[0]
dp={}
def dfs(i,k,p):
    if (i,k,p) in dp:
        return dp[(i,k,p)]
    if i==n:
        return 0
    res=float("inf")
    if k>0 and b[i]>p:
        res=min(res,p*(a[i+1]-a[i])+dfs(i+1,k-1,p))
    res=min(res,b[i]*(a[i+1]-a[i])+dfs(i+1,k,b[i]))
    dp[(i,k,p)]=res
    return res
print(a[1]*b[0]+dfs(1,k,b[0]))

C++ Code:

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define int long long
#define all(x) x.begin(), x.end()
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;

const int N = 5e2 + 5, mod = 1e9 + 7;
int tc, n, m, k, ans, a[N], dp[N][N], d[N], l;
string s, t;
bool flag, vis[N], pr[N];

int32_t main(){
    FASTER;
//    freopen("", "r", stdin);

    tc=1;
//    cin>>tc;
    while(tc--){
        cin>>n>>l>>k;
        d[n+1] = l;

        for(int i=1; i<=n; i++)cin>>d[i];
        for(int i=1; i<=n; i++)cin>>a[i];

        for(int i=0; i<=n+1; i++)
            for(int j=0; j<=k; j++)
                dp[i][j] = 1e10;

        dp[1][0] = a[1] * d[2];
        for(int i=2; i<=n+1; i++){
            for(int j=0; j<=min(i-2, k); j++){
                for(int lst=i-j-1; lst<i; lst++)
                    dp[i][j] = min(dp[i][j], dp[lst][j-i+lst+1] + (d[i] - d[lst+1]) * a[lst] + (d[i+1] - d[i]) * a[i]);
            }
        }
        ans = 1e10;
        for(int i=0; i<=k; i++)ans = min(ans, dp[n+1][i]);
        
        cout<<ans<<endl;
    }
    return 0;
}


Comments

Submit
0 Comments
More Questions

822B - Crossword solving
1623A - Robot Cleaner
884B - Japanese Crosswords Strike Back
862B - Mahmoud and Ehab and the bipartiteness
429A - Xor-tree
1675C - Detective Task
950A - Left-handers Right-handers and Ambidexters
672B - Different is Good
1C - Ancient Berland Circus
721A - One-dimensional Japanese Crossword
1715B - Beautiful Array
60B - Serial Time
453A - Little Pony and Expected Maximum
1715A - Crossmarket
1715C - Monoblock
1512C - A-B Palindrome
1679B - Stone Age Problem
402A - Nuts
792A - New Bus Route
221A - Little Elephant and Function
492C - Vanya and Exams
1369B - AccurateLee
892B - Wrath
999A - Mishka and Contest
727C - Guess the Array
1625C - Road Optimization
1715D - 2+ doors
267A - Subtractions
1582A - Luntik and Concerts
560A - Currency System in Geraldion